Khu vực nay là Johor Bahru nguyên mang tên Tanjung Puteri, và là một làng chài Mã Lai nằm gần Singapore. Temenggong Daeng Ibrahim sau đó đổi tên Tanjung Puteri sang Iskandar Puteri khi ông đến khu vực này vào năm 1858 sau khi giành được lãnh thổ từ Sultan Ali;[10] sau khi Temenggong qua đời thì Sultan Abu Bakar đổi tên khu vực thành Johor Bahru.[11] Người Anh ưu tiên viết tên khu vực là Johore Bahru hay Johore Bharu,[12] song hiện chấp thuận chính tả Johor Bahru, do Johore chỉ được viết là Johor trong tiếng Mã Lai.[13][14]

Thành phố cũng từng được cộng đồng người Hoa địa phương gọi là Tiểu Sán Đầu do hầu hết người Hoa tại đây là người Triều Châu có tổ tiên đến từ Sán Đầu vào giữa thập niên 1800, trong thời gian trị vì của Temenggong Daeng Ibrahim.[15]